#include <iostream>

using namespace std;

// 动态规划算法
int maxProductAfterCutting(int length){

    if ( length < 2 ){
        return 0;
    }else if ( length == 2 ){
        return 1;
    }else if ( length == 3 ){
        return 2;
    }

    int * data = new int[length+1];
    data[0] = 0;
    data[1] = 1;
    data[2] = 2;
    data[3] = 3;

    int max = 0;
    for ( int i = 4; i<=length ; i++ ){
        max = 0;
        for ( int j = 1; j<= i/2; j++ ){
            int product = data[j]*data[i-j];
            if ( max < product ){
                max = product;
            }
        }
        data[i] = max;
    }
    max = data[length];
    delete[] data;
    return max;
}


// 贪婪算法实现
int maxProductAfterCutting_solution2(int length){

    if ( length  < 2 )
        return 0;
    else if ( length == 2 )
        return 1;
    else if ( length == 3 )
        return 2;
    
    // 先尽可能的剪长度为３的绳子段
    int indexOf3 = length/3;

    // 将绳子剪成长度为２的绳子段
    if ( length - indexOf3 * 3 == 1 )
        indexOf3 -= 1;

    int indexOf2 = ( length - indexOf3*3 )/2;
    return (int)(pow(3, indexOf3)+pow(2, indexOf2));
}

int main(void){
    cout << "动态规划实现：　expect is 36: " << maxProductAfterCutting(10) << endl;
    cout << "贪心算法实现：　expect is 36: " << maxProductAfterCutting_solution2(10) << endl;
    return 0;
}